
/*
Ref: 

From an email from Chas Emerick to Michael Gilleland, 22 October 2003:

Mr. Gilleland,

As you may know, the Apache Jakarta Commons project had appropriated 
your sample implementation of the Levenshtein Distance algorithm for 
its commons-lang Java library.  While attempting to use it with two 
very large strings, I encountered an OutOfMemoryError, due to the fact 
that a matrix is created with the dimensions of the two strings' 
lengths.  I know you created the implementation to go with your 
(excellent) illustration of the algorithm, so this matrix approach 
translates that illustration and tutorial perfectly.

However, as I said, the matrix approach doesn't lend itself to getting 
the edit distance of two large strings.  For this purpose, I modified 
your implementation to use two single-dimensional arrays; this is 
clearly more memory-friendly (although it probably results in some very 
slight performance degradation when comparing smaller strings).

I've submitted the modification to the maintainers of the commons-lang 
project, and I've appended the relevant method below.

Thanks!

Chas Emerick  

http://www.merriampark.com/ldjava.htm

*/

package net.xfok.dict;

 public class Similarity {   
   
     private int min(int one, int two, int three) {   
         int min = one;   
         if(two < min) {   
             min = two;   
         }   
         if(three < min) {   
             min = three;   
         }   
         return min;   
     }   
        
     public int ld(String str1, String str2) {   
         int d[][];  //����   
         int n = str1.length();   
         int m = str2.length();   
         int i;  //����str1��   
         int j;  //����str2��   
         char ch1;   //str1��   
         char ch2;   //str2��   
         int temp;   //��¼��ͬ�ַ�,��ĳ������λ��ֵ������,����0����1   
         if(n == 0) {   
             return m;   
         }   
         if(m == 0) {   
             return n;   
         }   
         d = new int[n+1][m+1];   
         for(i=0; i<=n; i++) {    //��ʼ����һ��   
             d[i][0] = i;   
         }   
         for(j=0; j<=m; j++) {    //��ʼ����һ��   
             d[0][j] = j;   
         }   
         for(i=1; i<=n; i++) {    //����str1   
             ch1 = str1.charAt(i-1);   
             //ȥƥ��str2   
             for(j=1; j<=m; j++) {   
                 ch2 = str2.charAt(j-1);   
                 if(ch1 == ch2) {   
                     temp = 0;   
                 } else {   
                     temp = 1;   
                 }   
                 //���?1,�ϱ�+1, ���Ͻ�+tempȡ��С   
                 d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+temp);   
             }   
         }   
         return d[n][m];   
     }   
     
     // paire left most n
     // if right most m = l - n < DD display
     public int dd(String str1, String str2) {   
         int min ;   
         int max ;   
         int dd;  //����   
         int i;  //����str1��   
         char ch1;   //str1��   
         char ch2;   //str2��   
         
         String l;
         String s;
         
         if (str1.length() > str2.length()){
        	 l = str1;
        	 s = str2;
         }
         else{
        	 l = str2;
        	 s = str1;
         }
         max = l.length();
         min = s.length();
         
         if(max == 0) {   
             return min;   
         }   
         if(min == 0) {   
             return max;   
         }   
         
         for (i=0;i<min;i++){
        	 ch1 = str1.charAt(i);   
        	 ch2 = str2.charAt(i);
        	 if (ch1 != ch2){
        		 break;
        	 }
         }
         dd = min - 1 - i ;
         
         return dd;   
     }   
        
     public double sim(String str1, String str2) {   
         int ld = ld(str1, str2);   
         return 1 - (double) ld / Math.max(str1.length(), str2.length());    
     }   
        
     public static void testMain(String[] args) {   
         Similarity s = new Similarity();   
         String str1 = "chenlb.blogjava.net";   
         String str2 = "chenlb.javaeye.com";   
         System.out.println("ld="+s.ld(str1, str2));   
         System.out.println("sim="+s.sim(str1, str2));   
     }   
 } 